class Solution(object):
    def minPathSum(self, grid):
        m = len(grid)  # 行数
        n = len(grid[0])  # 列数

    # 初始化DP数组（直接在原网格修改以优化空间，不影响结果）
    # 第一行
        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]

    # 第一列
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]

    # 填充其他位置
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
        return grid[-1][-1]  # 右下角的DP值即为结果


if __name__ == "__main__":
    # 手动输入网格
    # 提示用户输入网格，支持[[x,x],[x,x]]格式
    print("请输入网格（格式示例：[[1,3,1],[1,5,1],[4,2,1]]）：")
    input_str = input().strip()
    grid = eval(input_str)
    solution = Solution()

    # 计算并输出结果
    result = solution.minPathSum(grid)
    print(result)